package uglyNumberII;



public class Solution {
    public int nthUglyNumber(int n) {
        int f1=2,f2=3,f3=5,n1=0,n2=0,n3=0;
        if (n==1) return 1;
        int[] list=new int[n+1];
        list[0]=1;
        int nth=1;
        while (true){
        	int newF1=f1*list[n1];
        	int newF2=f2*list[n2];
        	int newF3=f3*list[n3];
        	if ((newF1<=newF2) && (newF1<=newF3)) {n1++; list[nth]=newF1;}
        	if ((newF2<=newF3) && (newF2<=newF1)) {n2++; list[nth]=newF2;}
        	if ((newF3<=newF1) && (newF3<=newF2)) {n3++; list[nth]=newF3;}
        	nth++;
        	if (nth==n) return Integer.min(newF1, Integer.min(newF2, newF3));
        }
        
    }
	public static void main(String args[]){
		Solution so=new Solution();
		System.out.println(so.nthUglyNumber(11));
		}
}
/*264. Ugly Number II
 * 数学分析题
 * 题目大意：定义只含有质因子2,3,5的数字为丑陋数，求第n个丑陋数
 * 定理1：任意正整数都能被分解为唯一的一串质数乘积
 * 故对于丑陋数列的第n个数，其都可以被分解成为丑陋数列第i（i<n）个数x*2 or x*3 or x*5的形式
 * 问题：不漏任意一个丑陋数
 * 解：每次选择x*2 or x*3 or x*5最小的结果加入数组尾，再进行下一轮迭代
 * 
 *  
 */
